10047. LinkedList пересечение

Найдите точку пересечения двух связных списков. Верните указатель на вершину, в которой начинается пересечение двух связных списков.

Определение связного списка:

//Java

class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

}

}

// C++

class ListNode

{

public:

int val;

ListNode *next;

ListNode(int x) : val(x), next(NULL) {}

};

Реализуйте функцию intersection которая возвращает указатель на вершину, в которой начинается пересечение двух связных списков.

// Java

ListNode intersection(ListNode l1, ListNode l2)

// C++

ListNode* intersection(ListNode *l1, ListNode *l2)

Пример

Функция intersection должна вернуть указатель на вершину со значением 7.

РЕШЕНИЕ

связный список

Анализ алгоритма

Предположим, что входные списки имеют одинаковую длину. Тогда установим на головы каждого из них по указателю. Двигаем последовательно оба указателя на одну позицию вправо, пока они не будут указывать на одну и ту же ячейку памяти.

Однако в нашем случае длины списков могут быть разные. Пусть lenA и lenB – длины списков (их можно вычислить за O(n)). Установим два указателя на головы списков. Указатель, установленный на голову более длинного списка, продвинем на | lenA – lenB | позиций вперед. Далее действуем как будто бы списки имеют одинаковую длину.

Пример

Длина списка l₁ равна lenA = 7. Длина списка l₂ равна lenB = 5.

Установим указатели a = l₁, b = l₂. Двигаем указатель a на |7 – 5| = 2 позиций вперед.

Шаг за шагом двигаем указатели a и b на одну позицию вперед пока они не станут равными. Как только станет a = b, указатели будут указывать на точку пересечения.

Реализация алгоритма

ListNode *intersection(ListNode *l1, ListNode *l2)

{

Установим указатели a = l₁, b = l₂.

ListNode *a = l1, *b = l2;

int lenA = 0, lenB = 0;

Вычисляем длину lenA списка l₁.

while (a != NULL)

{

lenA++;

a = a->next;

}

Вычисляем длину lenB списка l₂.

while (b != NULL)

{

lenB++;

b = b->next;

}

Передвигаем соответствующий указатель на | lenA – lenB | позиций вперед.

a = l1; b = l2;

if (lenA > lenB)

{

for (int i = 0; i < lenA - lenB; i++)

a = a->next;

}

else

{

for (int i = 0; i < lenB - lenA; i++)

b = b->next;

}

Двигаем указатели a и b пока они не совпадут.

while (a != b)

{

a = a->next;

b = b->next;

}

Возвращаем указывать на точку пересечения.

return a;

}